package p234

import node.ListNode


class ReverseStragty : Stragty {
    override fun isPalindrome(head: ListNode?): Boolean {
        var root: ListNode? = head
        var fast: ListNode? = head
        var slow: ListNode? = head
        //中间节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next
            slow = slow!!.next
        }
        //反转部分
        if (fast != null) {
            slow = slow!!.next
        }

        var tempt = reverse(slow)
        while (root != null && tempt != null) {
            if (root.`val` != tempt.`val`) {
                return false
            }
            root = root.next
            tempt = tempt.next
        }

        return true
    }

    fun reverse(root: ListNode?): ListNode? {
        var pre: ListNode? = null
        var head: ListNode? = root

        while (head != null) {
            var tempt = head.next

            head.next = pre
            pre = head

            head = tempt
        }
        return pre
    }
}